package com.liang.leetcode.dp;

import java.util.Arrays;

/**
 * 343.整数拆分
 */
public class Dp06_IntegerBreak {
    public static void main(String[] args) {
        int n = 30;
        System.out.println(integerBreak2(n));
    }

    /**
     * 解法1：动态规划
     * 拆成两个数：j * (i-j)
     * 拆成三个及以上的数：j * dp[i-j]
     */
    public static int integerBreak(int n) {
        // dp[i] 表示拆分数字 i 可以得到的最大乘积
        int[] dp = new int[n + 1];
        dp[2] = 1;
        // 从 3 开始，遍历到 n，计算每个数字拆分得到的最大乘积
        for (int i = 3; i <= n; i++) {
            // j 从 1 开始拆分 i
            // dp[3] = max(1 * 2, 1 * dp[2]) = 2;
            // dp[4] = max(1 * 3, 1 * dp[3]) = 3; max(2 * 2, 2 * dp[2]) = 4
            for (int j = 1; j <= i / 2; j++) {
                // 更新 dp[i]，比较 j * (i - j) 和 j * dp[i - j] 两种拆分方式，取最大值
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        for (int i = 2; i <= n; i++) {
            System.out.print(dp[i] + ", ");
        }
        return dp[n];
    }

    /**
     * 解法2：记忆化搜索
     */
    public static int integerBreak2(int n) {
        // 初始化记忆化数组
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        memo[2] = 1;
        return breakInteger(n, memo);
    }

    private static int breakInteger(int n, int[] memo) {
        if (memo[n] != -1) {
            // 已经计算过，直接返回
            return memo[n];
        }

        int maxProduct = 0;
        // 尝试拆分n为j和(i-j)，或j和dp[i-j]
        for (int j = 1; j <= n / 2; j++) {
            maxProduct = Math.max(maxProduct, Math.max(j * (n - j), j * breakInteger(n - j, memo)));
        }

        // 记录结果
        memo[n] = maxProduct;

        return maxProduct;
    }
}
